package com.tarry.list;



import org.tarry.utils.NumberFormatUtils;

import java.util.*;

/**
 * ArrayList 和 LinkedList 相关效率比较
 * <p>
 *     <H2>插入性能比较</H4>
 *     <H3>头插法：</H3>
 *     使用头插法时，LinkedList要高于ArrayList，因为ArrayList每插入一个元素，都要进行移位操作。 <br>
 *     <H3>尾插法:</H3>
 *     使用尾插法时，当数量级不到千万时，LinkedList要高于ArrayList，但是当数量级达到千万级时，ArrayList要优一些。
 *     LinkedList每次添加元素的时候，会new一个Node对象来存新增加的元素，所以当数据量小的时候，这个时间并不明显，
 *     而ArrayList需要扩容，所以LinkedList的效率比较高，但是当ArrayList出现不需要扩容的时候，
 *     那么ArrayList的效率是比LinkedList要高的，当数据量很大的时候，new对象的时间大于扩容的时间，
 *     那么ArrayList的效率高过LinkedList。
 * </p>
 * <p>
 *     <H2>遍历：数量级千万，ArrayList遍历使用fori性能最佳，LinkedList fori不建议使用，性能极差，使用Stream.foreach效果略好</H2>
 *     List集合类型为[class java.util.ArrayList],for循环遍历[10,000,000]条数据，耗费时间为[10]ms  <br>
 *     List集合类型为[class java.util.ArrayList],for循环遍历[10,000,000]条数据，未跑出结果，机器性能慢 <br>
 *     List集合类型为[class java.util.ArrayList],Iterator遍历[10,000,000]条数据，耗费时间为[50]ms <br>
 *     List集合类型为[class java.util.LinkedList],Iterator遍历[10,000,000]条数据，耗费时间为[144]ms <br>
 *     List集合类型为[class java.util.ArrayList],Steam遍历[10,000,000]条数据，耗费时间为[88]ms <br>
 *     List集合类型为[class java.util.LinkedList],Steam遍历[10,000,000]条数据，耗费时间为[46]ms <br>
 * </p>
 */
public class ListDemo {
    public static void main(String[] args) {
        sort();
//        random();
    }

    /**
     * 顺序添加和访问数据
     */
    protected static void sort(){
        ArrayList arrayList = new ArrayList();
        LinkedList linkedList = new LinkedList();
        testAdd(arrayList);
        testAdd(linkedList);
        printSplitSimple();
        testEach(arrayList);
//        千万级、百万级：性能差
//        testEach(linkedList);
        printSplitSimple();
        testIterator(arrayList);
        testIterator(linkedList);
        printSplitSimple();
        testStream(arrayList);
        testStream(linkedList);
    }

    /**
     * 随机访问数组
     */
    protected static void random() {
        ArrayList arrayList = new ArrayList();
        LinkedList linkedList = new LinkedList();
        addFirst(arrayList);
//        addFirst(linkedList);
    }

    /**
     * ArrayList 使用头插法插入数据
     *
     * <p>
     * 十万量级 <br>
     * List集合类型为[class java.util.ArrayList],根据下标添加[100,000]条数据，耗费时间为[617]ms <br>
     * List集合类型为[class java.util.LinkedList],根据下标添加[100,000]条数据，耗费时间为[8]ms
     * </p>
     *
     * <P>
     * 百万量级 <br>
     * List集合类型为[class java.util.ArrayList],根据下标添加[1,000,000]条数据，耗费时间为[60106]ms <br>
     * List集合类型为[class java.util.LinkedList],根据下标添加[1,000,000]条数据，耗费时间为[130]ms
     * </P>
     * <p>
     *     千万级 <br>
     *     ArrayList 耗费超长时间没跑出结果，机器性能限制 <br>
     *     List集合类型为[class java.util.LinkedList],根据下标添加[10,000,000]条数据，耗费时间为[4258]ms
     * </p>
     * @param list
     */
    protected static void addFirst(ArrayList list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < LIST_SIZE; i++) {
            list.add(0,i);
        }
        System.out.printf("List集合类型为[%s],根据下标添加[%s]条数据，耗费时间为[%d]ms \n",
                list.getClass(),
                NumberFormatUtils.format2Str(LIST_SIZE),
                System.currentTimeMillis() - start);
    }

    /**
     * LinkedList 使用头插入插入数据
     * <p>
     *     List集合类型为[class java.util.LinkedList],根据下标添加[10,000,000]条数据，耗费时间为[4258]ms
     * </p>
     * @param list
     */
    protected static void addFirst(LinkedList list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < LIST_SIZE; i++) {
            list.addFirst(i);
        }
        System.out.printf("List集合类型为[%s],根据下标添加[%s]条数据，耗费时间为[%d]ms \n",
                list.getClass(),
                NumberFormatUtils.format2Str(LIST_SIZE),
                System.currentTimeMillis() - start);
    }

    protected static void printSplitSimple(){
        System.out.println("---------------------------");
    }

    /**
     *  list大小 十万量级
     */
//    private final static int LIST_SIZE = 100000;
            // 百万量级
    private final static int LIST_SIZE = 1000000;

    // 千万量级
//    private final static int LIST_SIZE = 10000000;

    /**
     * 测试list顺序添加元素的效率: 默认都是尾插法 <br>
     * <p>
     *     当数据量达到千万级时，LinkedList明显下降，此时ArrayList性能更优： <br>
     *     LinkedList每次添加元素的时候，会new一个Node对象来存新增加的元素，所以当数据量小的时候，这个时间并不明显，
     *     而ArrayList需要扩容，所以LinkedList的效率比较高，但是当ArrayList出现不需要扩容的时候，
     *     那么ArrayList的效率是比LinkedList要高的，当数据量很大的时候，new对象的时间大于扩容的时间，
     *     那么ArrayList的效率高过LinkedList。
     * </p>
     * <p>
     * List集合类型为[class java.util.ArrayList],顺序添加[1000000]条数据，耗费时间为[28]ms
     * <br>
     * List集合类型为[class java.util.LinkedList],顺序添加[1000000]条数据，耗费时间为[133]ms
     * </p>
     * @param list
     */
    public static void testAdd(List list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < LIST_SIZE; i++) {
            list.add(i);
        }
        System.out.printf("List集合类型为[%s],顺序添加[%s]条数据，耗费时间为[%d]ms \n",
                list.getClass(),
                NumberFormatUtils.format2Str(LIST_SIZE),
                System.currentTimeMillis() - start);
    }

    /**
     * fori形式遍历List<br>
     * <p>
     *     List集合类型为[class java.util.ArrayList],for循环遍历[10,000,000]条数据，耗费时间为[17]ms <br>
     *     使用fori遍历LinkedList效率极低
     * </p>
     * @param list
     */
    protected static void testEach(List list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            list.get(i);
        }
        System.out.printf("List集合类型为[%s],for循环遍历[%s]条数据，耗费时间为[%d]ms \n",
                list.getClass(),
                NumberFormatUtils.format2Str(list.size()),
                System.currentTimeMillis() - start);
    }

    /**
     * 使用迭代器进行遍历 <br>
     * <p>
     *     List集合类型为[class java.util.ArrayList],Iterator遍历[10,000,000]条数据，耗费时间为[81]ms <br>
     *     List集合类型为[class java.util.LinkedList],Iterator遍历[10,000,000]条数据，耗费时间为[161]ms
     * </p>
     * @param list
     */
    protected static void testIterator(List list){
        long start = System.currentTimeMillis();
        Iterator<List> listIterator = list.iterator();
        while (listIterator.hasNext()){
            listIterator.next();
        }
        System.out.printf("List集合类型为[%s],Iterator遍历[%s]条数据，耗费时间为[%d]ms \n",
                list.getClass(),
                NumberFormatUtils.format2Str(list.size()),
                System.currentTimeMillis() - start);
    }

    protected static void testStream(List list){
        long start = System.currentTimeMillis();
        list.stream().forEach( i -> {

        });
        System.out.printf("List集合类型为[%s],Steam遍历[%s]条数据，耗费时间为[%d]ms \n",
                list.getClass(),
                NumberFormatUtils.format2Str(list.size()),
                System.currentTimeMillis() - start);
    }

}
